#!/usr/bin/python
# Filename: step.py

# Steps of Stairs
# you can go 1 or 2 or 3 stairs in 1 step, list how many kinds of step-sequences can you finish N stairs.

def go_stairs(n):
    if n < 1: return 0
    elif n == 1: return 1
    elif n == 2: return 2
    elif n == 3: return 4
    else: return (go_stairs(n-1) + go_stairs(n-2) + go_stairs(n-3))

for i in range(10):
    print "go %d stairs: %d" %(i, go_stairs(i))
